package stack;

import java.util.Arrays;

public class bigStack {
    //大根堆
    //父节点:(i-1)/2;
    //左孩子:2*i+1;
    //右孩子:2*i+2;
    public static void main(String[] args) {
        int[] arr = {2,5,8,7,4,3,6,9,1};
        heapsort(arr);
        System.out.println(Arrays.toString(arr));
//        for(int i = arr.length ; i >= 0; --i){
//            smallHeap(arr,i,arr.length);
//        }
//        System.out.println(Arrays.toString(arr));
    }
    //堆排序
    public static void heapsort(int[] arr){
        if(arr == null || arr.length < 2){
            return ;
        }
        //首先建立大根堆
        for(int i=arr.length-1 ; i>=0 ; i--){
            smallHeap(arr,i,arr.length);
        }
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while(heapSize > 0){
            smallHeap(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }
    }
    //建立小根堆
    public static void smallHeap(int[] arr, int index, int size){
        int left = index * 2 + 1;
        while(left < size){
            //找出左右孩子中最小的
            int smallest = left+1 < size && arr[left] > arr[left+1] ? left+1 : left;
            if(arr[smallest] >= arr[index]){
                break;
            }else{
                swap(arr,smallest,index);
                index = smallest;
                left = index * 2 + 1;
            }
        }
    }

    //建立大根堆
    public static void bigHeap(int[] arr, int index, int size){
        int left = index*2+1;
        while(left < size){
            //找到左右孩子的最大值
            int largest = left+1 < size && arr[left] < arr[left+1] ? left+1 : left;
            if(arr[largest] <= arr[index]){
                break;
            }else{
                //交换孩子和根节点，再循环判断大根堆是否成立
                swap(arr,largest,index);
                index=largest;
                left = index*2+1;
            }
        }
    }
    //
    public static void swap(int[] arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
